6941. Sum of GCD

 

For the given n  positive integers a1, a2, …, an, find the sum of the GCD (greatest common divisor) of all possible pairs of these numbers.

 

Input. The first line contains the number of test cases t (1 < t < 100). Each test consists of one line containing the number n (1 < n < 100), followed by n positive integers. All input integers do not exceed 106.

 

Output. For each test, print the sum of the GCDs of all possible pairs on a separate line.

 

Sample input

Sample outupt

3

4 10 20 30 40

3 7 5 12

3 125 15 25

70

3

35

 

 

SOLUTION

GCD

 

Algorithm analysis

For each test, store the set of input numbers in the mas array. Then, for each pair (i, j) (0 ≤ i < j < m) calculate the GCD (mas[i], mas[j]) and add it to the overall sum.

 

Example

For the third test case, the answer is

GCD(125,15) + GCD(125,25) + GCD(15,25) = 5 + 25 + 5 = 35

 

Algorithm implementation

Store the input numbers in the m array.

 

#define MAX 110

int m[MAX];

 

The gcd function returns the greatest common divisor of the numbers a and b.

 

int gcd(int a, int b)

{

  return (!b) ? a : gcd(b, a % b);

}

 

The main part of the program. Read the number of test cases tests.

 

scanf("%d", &tests);

while (tests--)

{

 

Read the input data for each test case.

 

  scanf("%d", &n);

  for (i = 0; i < n; i++)

    scanf("%d", &m[i]);

 

Compute the desired sum in the variable res.

 

  res = 0;

 

Iterate through all possible pairs of indices (i, j) such that 0 ≤ i < j < n, and for each pair compute the GCD (m[i], m[j]) and add this value to res.

 

  for (i = 0; i < n; i++)

  for (j = i + 1; j < n; j++)

    res += gcd(m[i], m[j]);

 

Print the answer.

 

  printf("%d\n", res);

}

 

Python implementation

Read the number of test cases tests.

 

tests = int(input())

 

Read the input data for each test case.

 

for _ in range(tests):

  n, *lst = list(map(int, input().split()))

 

Compute the desired sum in the variable res.

 

  res = 0

 

Iterate through all possible pairs of indices (i, j) such that 0 ≤ i < j < n, and for each pair compute the GCD (lst[i], lst[j]) and add this value to res.

 

  for i in range(n):

    for j in range(i + 1, n):

      res += math.gcd(lst[i], lst[j])

 

Print the answer.

 

  print(res)